package 动态规划;

public class 斐波那契数列 {
    public static void main(String[] args) {
//        System.out.println(calculate(8));
        System.out.println(calculate2(5));
    }
    //1.暴力递归法
    public static int  calculate(int num){
        /*思路：
          1.f1 + f2 = f3 ... fn-2 + fn-1 = fn,f1 = 0,f2 = 1;
          2.num从上向下遍历，fnum = fnum-1 + fnum-2;
          3.当遍历到f1 ,f2 时，结束遍历，开始回溯累加求和
         */
        if(num == 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        return calculate(num-1) + calculate(num-2);
    }
    //2.去重递归法
    public static int calculate1(int num){
        int[] arr = new int[num+1];
        return recursion(arr,num);
    }
    private static int recursion(int[] arr,int num){
        if(num == 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        if (arr[num] != 0){
            return arr[num];
        }
        arr[num] = recursion(arr,num-1) + recursion(arr,num-2);
        return arr[num];
    }
    //3，动态规划法
    public static int  calculate2(int num){
        int pre = 0,last = 1;
        int res = 0;
        for (int i = 2; i <= num; i++) {
            res = pre + last;//f2 = f0 + f1;
            pre = last;//f0 = f1;
            last = res;//f1 = f2;
        }
        return res;
    }
}
